package leetcode_81_100;

import java.util.ArrayDeque;
import java.util.Deque;

public class largestRectangleArea_84 {
    /**
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     *
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        /**
         * 想法是，遍历每一个柱子，然后让它向左右寻找以它的高度组成的最大矩形
         * 有个测试几千个数字，超时了，真的烦，还觉得自己这个思路挺好
         * 左右寻找的复杂度是O(n),嵌套在循环中必然及其耗时
         */
        if(heights.length==1)
            return heights[0];
        int len=heights.length;
        int maxArea=0;  //最大面积
        for(int i=0;i<len;i++){
            int left=i,right=i,
                    area ; //以它的高度组成的最大矩形
            while (left>0 && heights[left-1]>=heights[i]){ //向左找
               --left;
            }
            while ( right<len-1 && heights[right+1]>=heights[i]){ //向右找
                ++right;
            }
            area=(right-left+1)*heights[i];
            if(area>maxArea)
                maxArea=area;
        }
        return maxArea;
    }

    /**
     * 优化的关键是优化左右寻找边界
     * 用单调栈可以方便确定每个柱子组成的最大矩形的两个边界
     *
     * 单调增栈存储即 一个单调连续的递增数组
     * 0,2,1,5,6,2,3,0
     * 栈内
     * [0,1]   处理2
     * [0,2,3,4]   处理 6
     * [0,2,3]   处理 5
     * 遍历每个柱体，但实际操作的是栈顶元素
     * 进行循环判断
     * 1，若当前的柱体高度大于等于栈顶柱体的高度，就直接将当前柱体入栈
     * 2，否则若当前的柱体高度小于栈顶柱体的高度，说明当前栈顶柱体找到了右边的第一个小于自身的柱体
     * 那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积，然后继续判断更新后的栈顶元素
     *
     */
    public int largestRectangleArea2(int[] heights) {
        // 这里为了代码简便，在柱体数组的头和尾加了两个高度为 0 的柱体。
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length);
        // 对栈中柱体来说，栈中的前一个柱体就是其「左边第一个小于自身的柱体」；
        Deque<Integer> stack = new ArrayDeque<>();
        int area = 0;
        for (int i = 0; i < tmp.length; i++) {
            // 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
            while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
                int h = tmp[stack.pop()];  //将栈顶元素出栈
                area = Math.max(area, (i - stack.peek() - 1) * h); // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积
            }
            stack.push(i); //存入坐标
        }
        return area;
    }
}
